<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
  <head>
    <meta charset="utf-8" />
    <meta name="generator" content="pandoc" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, user-scalable=yes"
    />
    <title>normal_distribution_quick_sort</title>
    <style type="text/css">
      code {
        white-space: pre-wrap;
      }
      span.smallcaps {
        font-variant: small-caps;
      }
      span.underline {
        text-decoration: underline;
      }
      div.column {
        display: inline-block;
        vertical-align: top;
        width: 50%;
      }
    </style>
  </head>
  <body>
    <h1 id="normal-distribution-quicksort">Normal Distribution QuickSort</h1>
    <p>
      Algorithm implementing QuickSort Algorithm where the pivot element is
      chosen randomly between first and last elements of the array and the array
      elements are taken from a Standard Normal Distribution. This is different
      from the ordinary quicksort in the sense, that it applies more to real
      life problems , where elements usually follow a normal distribution. Also
      the pivot is randomized to make it a more generic one.
    </p>
    <h2 id="array-elements">Array Elements</h2>
    <p>
      The array elements are taken from a Standard Normal Distribution , having
      mean = 0 and standard deviation 1.
    </p>
    <h4 id="the-code">The code</h4>
    <pre><code>&gt;&gt;&gt; import numpy as np
&gt;&gt;&gt; from tempfile import TemporaryFile
&gt;&gt;&gt; outfile = TemporaryFile()
&gt;&gt;&gt; p = 100 # 100 elements are to be sorted
&gt;&gt;&gt; mu, sigma = 0, 1 # mean and standard deviation
&gt;&gt;&gt; X = np.random.normal(mu, sigma, p)
&gt;&gt;&gt; np.save(outfile, X)
&gt;&gt;&gt; print(&#39;The array is&#39;)
&gt;&gt;&gt; print(X)</code></pre>
    <hr />
    <h4 id="the-distribution-of-the-array-elements.">
      The Distribution of the Array elements.
    </h4>
    <pre><code>&gt;&gt;&gt; mu, sigma = 0, 1 # mean and standard deviation
&gt;&gt;&gt; s = np.random.normal(mu, sigma, p)
&gt;&gt;&gt; count, bins, ignored = plt.hist(s, 30, normed=True)
&gt;&gt;&gt; plt.plot(bins , 1/(sigma * np.sqrt(2 * np.pi)) *np.exp( - (bins - mu)**2 / (2 * sigma**2) ),linewidth=2, color=&#39;r&#39;)
&gt;&gt;&gt; plt.show()</code></pre>
    <hr />
    <p>
      <img
        src="https://www.mathsisfun.com/data/images/normal-distrubution-large.gif"
      />
    </p>
    <hr />
    <hr />
    <p>–</p>
    <h2
      id="plotting-the-function-for-checking-the-number-of-comparisons-taking-place-between-normal-distribution-quicksort-and-ordinary-quicksort"
    >
      Plotting the function for Checking ‘The Number of Comparisons’ taking
      place between Normal Distribution QuickSort and Ordinary QuickSort
    </h2>
    <pre><code>&gt;&gt;&gt;import matplotlib.pyplot as plt


    # Normal Disrtibution QuickSort is red
&gt;&gt;&gt; plt.plot([1,2,4,16,32,64,128,256,512,1024,2048],[1,1,6,15,43,136,340,800,2156,6821,16325],linewidth=2, color=&#39;r&#39;)

    #Ordinary QuickSort is green
&gt;&gt;&gt; plt.plot([1,2,4,16,32,64,128,256,512,1024,2048],[1,1,4,16,67,122,362,949,2131,5086,12866],linewidth=2, color=&#39;g&#39;)

&gt;&gt;&gt; plt.show()</code></pre>
    <hr />
    <hr />
  </body>
</html>
